package com.singzi.leetcode.N500;

import java.util.*;

public class T0497 {

}
class Solution0497 {

    int [][]matrix;
    TreeMap<Integer, Integer> map;
    int sum;
    Random random;
    public Solution0497(int[][] rects) {
        random = new Random();
        map = new TreeMap<>();
        sum = 0;
        matrix = rects;
        for(int i = 0;i < matrix.length;i++){
            sum += (matrix[i][2] - matrix[i][0] + 1)*(matrix[i][3] - matrix[i][1] + 1);
            map.put(sum, i);
        }

    }

    public int[] pick() {
        Queue<Integer>queue = new LinkedList<>();

        System.out.println(map.lastKey());
        int num = random.nextInt(map.get(map.lastKey()));
        num = map.ceilingKey(num);
        num = map.get(num);
        return new int[]{random.nextInt(matrix[num][2] - matrix[num][0] + 1) + matrix[num][0],
                random.nextInt(matrix[num][3] - matrix[num][1] + 1) + matrix[num][1]};

    }
}
